1. Field of the Invention
The present invention relates to a node device for transferring packets by attaching priority information, a node device for processing packets attached with priority information, and a packet transfer method using priority information attached to packets.
2. Description of the Background of the Art
A mechanism for guaranteeing QoS (Quality of Service) in IP (Internet Protocol) network has been proposed in a form of providing a constant QoS with respect to individual TCP/UDP session, based on an approach disclosed in R. Braden, L. Zhang, S. Berson. S. Herzog and S. Jamin,, xe2x80x9cResource ReSerVation Protocol (RSVP)xe2x80x94Version I Functional Specificationxe2x80x9d, Internet RFC 2205, September 1997; J. Wroclawski, xe2x80x9cSpecification of the Controlled-Load Network Element Servicexe2x80x9d, Internet RFC 2211, September 1997; and S. Shenker, C. Partridge and R. Guerin, xe2x80x9cSpecification of Guaranteed Quality of Servicexe2x80x9d, Internet RFC 2212, September 1997. However, this approach has been associated with a problem of scalability because it is necessary for each router of the network to maintain a state with respect to individual session so that it has been considered rather difficult to employ this approach in a large scale network.
Instead, there is a proposition of a framework called Differentiated Service (DS). The goal of DS is provide a mechanism in which the quality of service can be changed according to an amount of money paid by a user as simply as possible. At the data transfer level, a TOS (Type Of Service) field of the packet header is used in order to distinguish different QoSs, rather than having a state for each session in the network.
As for the priority bit to be used in the TOS field, there are a scheme for using just one bit as disclosed in D. Clark and J. Wroclawski, xe2x80x9cAn Approach to Service Allocation in the Internetxe2x80x9d, Internet Draft, draft-clark-diff-svc-alloc-00.txt, July 1997, and a scheme for using plural bits as disclosed in K. Kilkki, xe2x80x9cSimple Integrated Media Access (SIMA)xe2x80x9d, Internet Draft, draft-kalevi-simple-media-access-01.txt, June 1997.
The basic scheme of DS is as follows. A subscribed rate is specified between a user and a network or between two neighboring management networks (domains), and packets are marked as high priority packets while the transmission rate is less than or equal to the subscribed rate, or as low priority packets when the transmission rate exceeds the subscribed rate, according to a relationship between the subscribed rate and the monitored packet transmission rate. Then, the high priority packets are handled with priority over the low priority packets within the network or domain so as to provide different QoSs. Here, the marking is done by attaching (writing) an information indicating the priority level to the packet.
In the present specification, the subscribed rate between a user and a network will be referred to as an edge level rate (ELR) and the subscribed rate between two neighboring domains will be referred to as a domain level rate (DLR).
FIG. 1 shows an exemplary network to which DS is applied. In FIG. 1, U1, U2 and U3 are users (user terminals or user networks), E1 and E2 are edge routers, B1, B2, B3, B4, B5 and B6 are domain border routers, and R1 is a relay router. FIG. 1 shows a case involving four domains A, B, C and D. For instance, a network managed by one ISP (Internet Service Provider) corresponds to one domain.
Suppose that users U1, U2 and U3 in the domain A have subscribed edge level rates (ELR) of 2 Mbps, 2 Mbps and 5 Mbps, respectively, with respect to the domain A. In FIG. 1, only the subscribed rate for one direction is indicated for the sake of simplicity but it is possible to have the subscribed rate for both directions. It is assumed that the user is allowed to carry out the marking of high/low priority levels with respect to transmission packets at will. The edge routers E1 and E2 measure the arrival rate of the transmission packets from the user, and marks those high priority packets that arrived at rate above the subscribed edge level rate as low priority ones.
Then, suppose that the domain level rate (DLR) of 5 Mbps has been subscribed for traffic passing from the domain A to the domain B, for example. In FIG. 1, only the subscribed rate for one direction is indicated for the sake of simplicity but it is possible to have the subscribed rate for both directions. The domain border router B2 measures the arrival rate of packets from the domain A, and marks those high priority packets that arrived from the domain border router B1 at rate above the DLR as low priority ones. Similarly, when the DLR of 2 Mbps has been subscribed for traffic passing from the domain B to the domain C, the domain border router B5 marks those high priority packets that arrived from the domain border router B3 at rate above the DLR as low priority ones. Also, when the DLR of 10 Mbps has been subscribed for traffic passing from the domain B to the domain D, the domain border router B6 marks those high priority packets that arrived from the domain border router B4 at rate above the DLR as low priority ones.
Now, consider the case of using only one bit of the priority bit in FIG. 1. In this case, both the edge routers and the domain border routers will rewrite the same priority bit at a time of marking.
When the receiving rate of the high priority packets is above the subscribed rate at the domain level, the high priority packets below the subscribed rate will be passed as they are while packets above the subscribed rate will be marked as low priority ones regardless of whether they are originally high priority ones or low priority ones.
Suppose now that the user U1 transmitted the high priority packets destined to a host in the domain C at the ELR value of 2 Mbps. Also suppose that no transmission packets other than those from the user U1 are flowing from the domain border router B3 to the domain border router B5. Then, if the total transmission rate of the high priority packets from the users U2 and U3 is less than or equal to 3 Mbps, all the high priority packets from the user U1 will be delivered to the domain C as they are.
However, if the users U2 and U3 also transmit the high priority packets to the domain D and the total transmission rate of the high priority packets from the users U2 and U3 exceeds 3 Mbps, a part of the high priority packets from the user U1 will be changed into the low priority packets. In this case, there is a problem in that these high priority packets from the user U1 which are changed into the low priority packets at the domain border router B2 will be handled as the low priority ones in the domain C as well even if the domain border router B5 of the domain C has enough margin to pass 2 Mbps of the high priority packets from the user U1.
This problem is also present in the case of using plural priority bits as long as the same plural bits are to be rewritten at both the edge level and the domain level similarly as in the case of using one priority bit.
It is therefore an object of the present invention to provide a mechanism for a packet transfer scheme that applies markings at different levels to packets while they are transferred from their source to destination, in which a marking information at one level will not be lost by a marking at another level.
In order to achieve this object, the present invention provides a plurality of regions to which the priority information can be attached in a packet in correspondence to the plural levels, such that a region corresponding to one level will not be rewritten by a node that carries out the marking at another level.
A node device according to the present invention is thus characterized by writing the priority information according to criteria of the own node into a region in a packet into which the own node is allowed to write the priority information among the plurality of regions to which the priority information can be written, and transmitting that packet to a next hop node while maintaining the priority information in the other regions as received.
For example, when this node device is an edge router for transferring packets from a user (user terminal or user network) to a network, this node device writes the priority information into a region corresponding to the edge level (which can be considered as a network level in the case of using only two hierarchical levels of a user level and a network level), according to a rate specified between the user and the network for instance, without rewriting the priority information in a region corresponding to the user level. In addition, when there are three hierarchical levels of a user level, an edge level and a domain level, this edge router may writes the priority information into a region corresponding to the domain level, according to a policy of a domain to which this edge router belongs for instance. Else, when there are three hierarchical levels of a user level, an edge level and a neighboring node level, this edge router may writes the priority information into a region corresponding to the neighboring node level, according to a rate specified between this edge router and a next hop node.
Also, when this node device is a domain border router for transferring packets from one domain to another domain, this node device writes the priority information into a region corresponding to the domain level, according to a rate specified between domains or a policy of one of the domains to which this domain border router is connected for instance, without rewriting the priority information in any existing regions corresponding to the user level and the edge level (which includes the case where a value to be written by this domain border router happens to be the same as a value written in the same region by a previous hop domain border router so that it is left unchanged). Note that when there is only one level of either the user level or the edge level besides the domain level (as in the case where the edge router is to rewrite a region corresponding to the user level and no region corresponding to the edge level is provided for example), the priority information in a region corresponding to that one existing level is not to be rewritten by this domain border router. Also, when the neighboring node level also exists, this domain border router may write the priority information into a region corresponding to the neighboring node level, according to a rate specified between this domain border router and a next hop node.
Also, when this node device is a device for transferring packets from a previous hop node to a next hop node and a region corresponding to the neighboring node level exists, this node device writes the priority information into a region corresponding to the neighboring node level, according to a rate specified between this node and the next hop node for instance, without rewriting the priority information in any existing regions corresponding to the user level, the edge level, and the domain level (which includes the case where a value to be written by this node device happens to be the same as a value written in the same region by a previous hop node so that it is left unchanged).
As such, according to the present invention, packets are transferred while the priority information corresponding to one level is rewritten by a node that carries out the marking at the same level but not by a node that carries out the marking at another level. Namely, while packets are transferred from a source to a destination, the priority information corresponding to the domain level for instance will be rewritten every time packets are transferred across a range in which the priority information of that level is valid (i.e., a border of that domain), and the priority information corresponding to the neighboring node level for instance will be rewritten every time packets are transferred across a range in which the priority information of that level is valid (i.e., a next hop node), while the priority information corresponding to the user level for instance will not be rewritten within a range in which the priority information of that level is valid (i.e., until packets are received by the user).
By utilizing such hierarchical priority information, each node through which packets pass can carry out a flexible priority control reflecting an intention of the user or a policy of the domain, as in the following examples.
One example of the priority control is the priority control at a time of attaching the priority information. Namely, a transmission unit of this node device can determine the priority information to be written by the own node according to the priority level specified by one or a combination of plural of the priority information written in a plurality of regions contained in the received packet.
At this point, the priority information to be written can be determined according to the priority level specified as described above such that an amount of communication resources to be used by selected packets, which are to be transmitted by writing the priority information indicating the high priority into a region to which the own node is allowed to attach the priority information, will approach an amount of communication resources allocated to a set of packets to which these selected packets belong. Here, the reference amount of communication resources should preferably be that which is allocated within a range in which the priority information attached by the own node is valid (such as within the domain, or between neighboring nodes).
Note that this provision of determining the priority information according to the allocated amount of communication resources is valid even in the case where the edge router transmits a received packet by rewriting the priority information in a region corresponding to the user level instead of maintaining it. In such a case, the reference amount of communication resources can be an amount of communication resources allocated between the user and the network.
In order to make the amount of communication resources to be used by a packet which is to be written as the high priority one by the own node approaching to the reference amount, there can be a case where that packet is written as the low priority one even when a referenced region (which can be a region to which the own node is allowed to write the priority information or a region to which the own node is not allowed to write the priority information) indicates the high priority (the case of having many high priority packets) as well as a case where that packet is written as the high priority one even when the referenced region indicates the low priority (the case of having few high priority packets). As described below, there are many possible variations regarding how to determine the priority level at a time of attaching the priority information according to referenced one or plural priority information, and regarding how to use the determined priority level in relation to the reference amount in determining the priority information to be attached.
Another example of the priority control is the priority control at a time of packet transfer. Namely, a node device (which by itself does not attach the priority information) on a transfer route of a packet transmitted by the above described node device which attaches the priority information can carry out the transfer processing for that packet (including packet discarding or delay control) according to the priority level specified by referring to one or plural of the plurality of regions in which the respective priority information is written in that packet as received. Here, in the case of carrying out the packet discarding, the controlling is made such that packets with higher priority level will be less likely to be discarded, and in the case of carrying out the delay control, the controlling is made such that packets with higher priority level will be delayed shorter.
Note that when the node device which attaches the priority information itself transmits (transfers) the received packet, this node device may carry out the priority control related to the packet transfer according to the priority information written in that received packet, or according to the priority information written by the own node, or else by using another mechanism unrelated to the priority information in the packet. Also, a way of determining the priority level at a time of attaching the priority information and a way of determining the priority level at a time of packet transfer may be the same or different.
Note also that each aspect of the present invention described herein as a feature of a node device can be also conceived as a feature of a packet transfer method or an article of manufacture storing programs for causing the computer to function as the node device or to execute steps of the packet transfer method.
Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.